1. Field of the Invention
This invention relates to sorting mechanism in a computer, and more particularly relates to a dual reciprocating pipelined sorter which overlaps two sorting operations with each other and with input/output required operations so as to require a zero time increment for the two sorting operations.
2. Description of the Prior Art
Sorting is one of the most important operations in data processing. It is estimated that in data processing centers, over 25 percent of central processing unit (CPU) time is devoted to sorting. Many sequential and parallel sorting algorithms, and various sorting structures implementing these algorithms, have been proposed, studied and built.
U.S. Pat. No. 4,110,837, Chen, APPARATUS FOR THE SORTING OF RECORDS OVERLAPPED WITH LOADING AND UNLOADING OF RECORDS INTO A STORAGE APPARATUS, August 1978, shows a computer sorting technique in which an unordered group of items enter into a sorter stack and trickle down in a semi-sort. When all the items have been entered into the sorter stack the second semi-sort is accomplished as the items trickle up for exit out of the sorter stack in fully sorted sequence. These operations take place during the same time that input and output operations may be taking place. There is no discernible sorting time, the sorting being completely overlapped by the loading and unloading of information records. Chen does not show any technique for carrying out a sorting operation of a second unordered group of items overlapped with the sorting operation of the group of items which he is sorting.
Other sorting techniques and variations are included in the following U.S. patents:
U.S. Pat. No. 3,997,880, Chen et al, APPARATUS AND MACHINE IMPLEMENTABLE METHOD FOR THE DYNAMIC REARRANGEMENT OF PLURAL BIT EQUAL-LENGTH RECORDS, December, 1976. Chen et al shows an apparatus for performing efficient transposition exchange sorts among equal length records taking advantage of the flow steering property of linkable circulating storage loops to minimize average access time by positioning information closer to the output port. PA0 U.S. Pat. No. 4,090,249, Chen et al, APPARATUS FOR SORTING RECORDS IN OVERLAP RELATION WITH RECORD LOADING AND EXTRACTION, May 1978. Chen et al shows a record exchange sorter with comparison circuits to control exchange of records being advanced along a linear array from the input to the output.
The literature includes a great number of articles discussing various techniques for sorting. For example, A. W. Maholick and R. E. Snyder, SORTING NETWORK, IBM Technical Disclosure Bulletin, Vol. 12, #4, September 1969, p. 620, describes an interchange sorter which sorts by comparing and interchanging data words. Repetition of this cycle results in the shifting or non-shifting of the data words so that the words are stored in order of magnitude with the highest term in the exit register.
The prior art does not disclose a sort mechanism in which more than one unordered group of items is undergoing processing in the sorter stack at the same time.